#pragma once

#include<vector>
using namespace std;

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int j = 0, k = nums.size() - 1;
        int i = 0;
        int value = nums[i] * (-1);
        int value1 = nums[j];
        int value2 = nums[k];

        while (i < nums.size())
        {
            j = i + 1;
            k = nums.size() - 1;
            while (j < k)
            {
                if (nums[i] > 0)
                    break;
                value = nums[i];
                int tmp = value * (-1);
                value1 = nums[j];
                value2 = nums[k];
                if (value1 + value2 > tmp)
                {
                    --k;
                }
                else if (value1 + value2 < tmp)
                {
                    ++j;
                }
                else
                {
                    ret.push_back({ nums[i] , nums[j] , nums[k] });
                    ++j;
                    while (j < k && nums[j - 1] == nums[j])
                    {
                        ++j;
                    }
                    --k;
                    while (k > j && nums[k + 1] == nums[k])
                    {
                        --k;
                    }
                }
            }
            ++i;
            while (i < nums.size() && nums[i - 1] == nums[i])
            {
                ++i;
            }
        }
        return ret;
    }
};